package main

//### day4
//
//#### 669. 修剪二叉搜索树
//
//https ://leetcode.cn/problems/trim-a-binary-search-tree/
//

//
//```go
func trimBST(root* TreeNode, low int, high int)* TreeNode {
	if root == nil{
		return nil
	}
	if root.Val < low{
		return trimBST(root.Right, low, high)
	}
	else if root.Val > high{
		return trimBST(root.Left, low, high)
	}
	else {
		root.Left = trimBST(root.Left, low, high)
		root.Right = trimBST(root.Right, low, high)
		return root
	}
}
//```
//
//#### 108. 将有序数组转换为二叉搜索树
//
//https ://leetcode.cn/problems/convert-sorted-array-to-binary-search-tree/

//```go
func sortedArrayToBST(nums[]int)* TreeNode {
	return dfs(nums, 0, len(nums) - 1)
}
func dfs(nums[]int, left, right int)* TreeNode {
	if left > right{
		return nil
	}
mid: = (right - left) / 2 + left
root : = &TreeNode{ Val: nums[mid] }
	root.Left = dfs(nums, left, mid - 1)
	root.Right = dfs(nums, mid + 1, right)
	return root
}
//```
//
//#### 538. 把二叉搜索树转换为累加树
//
//https ://leetcode.cn/problems/convert-bst-to-greater-tree/
//

//```go
func convertBST(root* TreeNode)* TreeNode {
sum: = 0
	var dfs func(*TreeNode)
	dfs = func(node * TreeNode) {
		if node != nil{
			dfs(node.Right)
			node.Val += sum
			sum = node.Val
			dfs(node.Left)
		}
	}
	dfs(root)
	return root
}
//```
